// 21. Merge Two Sorted Lists

// Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

package main

type ListNode struct {
	Val  int
	Next *ListNode
}

func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
	if l1 == nil {
		return l2
	}

	if l2 == nil {
		return l1
	}

	step1, step2 := l1, l2
	l, current := step1, step1
	if step1.Val <= step2.Val {
		step1 = step1.Next
	} else {
		l, current = step2, step2
		step2 = step2.Next
	}

	for step1 != nil && step2 != nil {
		if step1.Val <= step2.Val {
			current.Next = step1
			current = current.Next
			step1 = step1.Next
			continue
		}

		current.Next = step2
		current = current.Next
		step2 = step2.Next
	}

	if step1 == nil && step2 == nil {
		return l
	}

	if step1 != nil {
		current.Next = step1
	} else {
		current.Next = step2
	}

	return l
}

func (l *ListNode) printNode() {
	i := 1
	for l != nil {
		println("i=", i, "v=", l.Val)
		l = l.Next
		i++
	}
}

func main() {
	h, h1, i := new(ListNode), new(ListNode), 1
	head, head1 := h, h1
	for i < 3 {
		h.Val, h1.Val = i, i
		h.Next, h1.Next = new(ListNode), new(ListNode)
		h, h1 = h.Next, h1.Next
		i++
	}
	h.Val, h1.Val = i, i

	head.printNode()
	println("==========")
	head1.printNode()
	l := mergeTwoLists(head, head1)
	println("=====------=====")
	l.printNode()
}
